package leetcode.editor.cn;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class _139_WordBreak {
    public static void main(String[] args) {
        Solution solution = new _139_WordBreak().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> set = new HashSet<>(wordDict);
            int n = s.length();
            boolean[] dp = new boolean[n + 1];
            dp[0] = true;

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= i; j++) {
                    if (dp[j - 1] && set.contains(s.substring(j - 1, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[n];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}